1. Field of the Invention
The present invention relates to a method and system for the computer-supported determination of a route from a starting point to a destination point wherein the route is determined from a plurality of sub-routes which, in turn, are determined from a plurality of sub-modules respectively associated with the starting point and destination point.
2. Description of the Prior Art
The invention is directed to the determination of a route from a starting point to a destination point.
What is of concern in computer-supported route planning systems is to determine a route between a prescribable starting point, i.e. a departure location at which a user of the route planning system would like to begin a trip, and a destination point to which the user would like to travel. Such determination should be done in such a way that the determination of the route itself occurs as quickly as possible and the route is optimized in view of various, prescribable requirements. Requirements in this sense can be, for example, a travel time required for the overall route, the route length, or specific particulars with regard to specific means of transportation which are preferably are to be utilized.
What is to be understood below by a route is a path description, i.e. a set of nodes and edges, when the path is represented by a graph that includes such nodes and edges, from a starting point to a destination point. The determination of the route should be implemented optimally quickly and flexibly. An overview of methods for determining shortest paths can be found, for example, in B. V. Cherkassky et al., Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, No. 2, pp. 129-174, 1993.
B. V. Cherkassky et al, Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, No. 2, pp. 129-174, 1996.
In accordance with the teachings of the present invention, therefore, the route from a starting point to a destination point is determined in an iterative method. The starting point and the destination point lie in different sub-route maps, wherein the sub-route maps are stored in digital form. The method includes the following steps:
sub-modules that are respectively allocated to a sub-route map are supplied with digital messages that respectively contain at least one sub-starting point and at least one sub-destination point that lie in the sub-route map of the sub-module that receives the respective message;
each sub-module determines at least one sub-route between the respective sub-starting point and the sub-destination point; and
the route is formed from the sub-route.
The system includes a processor unit that is configured such that a route from a starting point to a destination point that respectively lie in different sub-route maps is determined in an iterative method, wherein the sub-route maps are stored in digital form. The system includes the following:
sub-modules that are respectively allocated to a sub-route map which are supplied with digital messages that respectively contain at least one sub-starting point and at least one sub-destination point that lie in the sub-route map of the sub-module that receives the respective message;
at least one sub-route between the respective sub-starting point and the sub-destination point which is determined by each sub-module; and
the route which is formed from the sub-routes.
The present invention assures a fast, flexible determination of a route for a user from a prescribable starting point to a prescribable destination point (at a prescribable point in time). The extremely complex problem of route determination is thereby split into sub-problems that are respectively solved independently of one another. As a result a it becomes possible to consider both central and local knowledge in secondary conditions of determining sub-routes or, respectively, the route.
It is advantageous in one development of the present invention that the sub-route maps are stored in the form of sub-route graphs having nodes and edges, wherein a method for determining shortest paths is respectively utilized for the determination of the sub-route. By utilizing the methodology of determining shortest paths, it is possible to form optimized sub-routes in view of the prescribable optimization criteria in the individual sub-modules in a simple way. The use of methods for determining shortest paths is to be understood such that a respective sub-route is determined optimized in view of a predetermined cost function (optimization criteria). Respective cost values that correspond to the predetermined optimization criterion are allocated to the edges.
Prescribable optimization criteria also can be, for example, the minimization of turning events, particularly left-turn events in cities, in addition to the path length or the duration of a route. Further, the point in time for which the route is to be planned can be taken into consideration in the present invention. Thus, for example, the time of the trip definitely can be of significance since the decision of selecting individual transportation or public transportation for the route can be dependent on the selected point in time (during rush hour one will presumably need more time with an automobile in a central city than given employment of public transportation; the situation might be exactly opposite at night).
An exemplary embodiment of the present invention is shown in the Figures and is explained in greater detail below.